package DynamicProgramming;

public class _486_PredicttheWinner {
    public boolean PredictTheWinner(int[] nums) {
        int[][] dp = new int[nums.length][nums.length];
        for (int i = nums.length; i >= 0; i--) {
            for (int j = i + 1; j < nums.length; j++) {
                int a = nums[i] - dp[i + 1][j];
                int b = nums[j] - dp[i][j - 1];
                dp[i][j] = Math.max(a, b);
            }
        }
        return dp[0][nums.length - 1] >= 0;
    }
}
